package com.colter.project.data.structure.sort;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {
	public static void main(String[] args) {
		Random random = new Random();
		int[] nums = new int[10];
		for (int i = 0; i < nums.length; i++) {
			nums[i] = random.nextInt(100);
		}

		System.out.println(Arrays.toString(nums));

		int[] result = quickSort(nums, 0, nums.length - 1);
		System.out.println(Arrays.toString(result));
	}

	public static int[] sort(int[] nums) {
		return quickSort(nums, 0, nums.length - 1);
	}

	public static int[] quickSort(int[] arr, int low, int high) {
		int start = low + 1;
		int end = high;

		if (low >= arr.length) {
			return arr;
		}
		int key = arr[low];
		while (start < end) {
			while (start < end && arr[end] > key) {
				end--;
			}
			while (start < end && arr[start] <= key) {
				start++;
			}

			if (start < end) {
				int temp = arr[start];
				arr[start] = arr[end];
				arr[end] = temp;
			}
		}

		int midIndex = low;
		if (start == end) {
			if (key > arr[start]) {
				arr[low] = arr[start];
				arr[start] = key;
				midIndex = end;
			}

		}

		if (low < high) {
			quickSort(arr, low, midIndex - 1);
			quickSort(arr, midIndex + 1, high);
		}

		return arr;
	}

}
